import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 面试题68-2：二叉树的最近公共祖先
 */
public class Offer_68_II {
    /**
     * 方法三：递归
     * <p>
     * 当我们用递归去做这个题时不要被题目误导，应该要明确一点
     * 这个函数的功能有三个：给定两个节点 p 和 q
     * 1. 如果 p 和 q 都存在，则返回它们的公共祖先；
     * 2. 如果只存在一个，则返回存在的一个；
     * 3. 如果 p 和 q 都不存在，则返回 null
     * 本题说给定的两个节点都存在，那自然还是能用上面的函数来解决
     * 
     * 具体思路：
     * （1） 如果当前结点 root 等于 null，则直接返回 null
     * （2） 如果 root 等于 p 或者 q ，那这棵树一定返回 p 或者 q
     * （3） 然后递归左右子树，因为是递归，使用函数后可认为左右子树已经算出结果，用 left 和 right 表示
     * （4） 此时若left为空，那最终结果只要看 right；若 right 为空，那最终结果只要看 left
     * （5） 如果 left 和 right 都非空，因为只给了 p 和 q 两个结点，都非空，说明一边一个，因此 root 是他们的最近公共祖先
     * （6） 如果 left 和 right 都为空，则返回空（其实已经包含在前面的情况中了）
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root.val == p.val || root.val == q.val) {
            return root;
        }

        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        // left、right 任一为空，说明位于另一子树中
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        // left、right 都非空，说明分居 root 两侧，root 即是答案
        return root;
    }

    /********************************************************/

    TreeNode ans = null;

    /**
     * 方法二：递归（LeetCode官方题解）
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public TreeNode lowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root, p, q);
        return ans;
    }

    /**
     * 我们递归遍历整棵二叉树，定义 f_x 表示 x 节点的子树中是否包含 p 节点或 q 节点，
     * 如果包含为 true，否则为 false。
     * 那么符合条件的最近公共祖先 x 一定满足如下条件：
     *     (f_lson && f_rson) || ((x == p || x == q) && (f_lson || f_rson))
     * 其中 lson 和 rson 分别代表 x 节点的左孩子和右孩子。
     * 
     * 初看可能会感觉条件判断有点复杂，我们来一条条看，
     * f_lson && f_rson 说明左子树和右子树均包含 p 节点或 q 节点，
     * 如果左子树包含的是 p 节点，那么右子树只能包含 q 节点，反之亦然，
     * 因为 p 节点和 q 节点都是不同且唯一的节点，
     * 因此如果满足这个判断条件即可说明 x 就是我们要找的最近公共祖先。
     * 
     * 再来看第二条判断条件，这个判断条件即是考虑了 x 恰好是 p 节点或 q 节点
     * 且它的左子树或右子树有一个包含了另一个节点的情况，
     * 因此如果满足这个判断条件亦可说明 x 就是我们要找的最近公共祖先。
     */
    public boolean dfs(TreeNode node, TreeNode p, TreeNode q) {
        if (node == null) {
            return false;
        }
        boolean leftSon = dfs(node.left, p, q);
        boolean rightSon = dfs(node.right, p, q);
        if ((leftSon && rightSon) || ((node.val == p.val || node.val == q.val) && (leftSon || rightSon))) {
            ans = node;
        }
        return leftSon || rightSon || (node.val == p.val || node.val == q.val);
    }

    /********************************************************/

    // key 为节点值，value 为其父节点
    Map<Integer, TreeNode> parent = new HashMap<>();
    // 已访问过的节点
    Set<Integer> visited = new HashSet<>();

    /**
     * 方法一：哈希表存储父节点
     * <p>
     * 相当于给节点添加了指向父节点的指针，把问题转化成寻找两个链表的第一个公共节点
     * <p>
     * 时间复杂度：O(n)
     * <p>
     * 空间复杂度：O(n)
     */
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        dfs(root);
        while (p != null) {
            visited.add(p.val);
            p = parent.get(p.val);
        }
        while (q != null) {
            if (visited.contains(q.val)) {
                return q;
            }
            q = parent.get(q.val);
        }
        return null;
    }

    public void dfs(TreeNode root) {
        if (root.left != null) {
            parent.put(root.left.val, root);
            dfs(root.left);
        }
        if (root.right != null) {
            parent.put(root.right.val, root);
            dfs(root.right);
        }
    }
}
